Markov chain usage models have proven to be valuable tools in software testing as well as in modeling software-engineering processes. As is known in the art, the Markov chain usage model may be represented as a square matrix where each element represents a probability of transition from a present state, which is represented along the row of the matrix, to a future state, which is represented along the column of the matrix. In other words, given a present state i and a future state j, the matrix element pij provides the probability of transition from i to j. Since all events from any one state must either remain in that state or move to another state, the sum of the probabilities in each row is exactly 1.0.
As is known, submodels may be substituted for states within a Markov chain usage model similar to how program modules may be substituted for certain lines of computer code in modular programming. Markov chain usage models, in which submodels are nested, are often referred to as “hierarchical models” due to the resulting hierarchical structure from the nested submodels. Thus, if a submodel appears as a node in the Markov chain usage model, then the transient submatrix of a Markov chain usage model may be represented as M=[mij], and the transient submatrix of a submodel of M may be represented as S=[sij]. Typically, an analysis of a hierarchical model involves flattening of the model by instantiating S in M, thereby generating a flattened model F. The transient submatrix of the flattened model may be represented as F=[fij].
Each of the transient sub-matrices M, S, and F has a corresponding first moment matrix NM, NS, and NF, respectively, where:NM=(I−M)−1  [Eq. 1],NS=(I−S)−1  [Eq. 2],andNF=(I−F)−1  [Eq. 3],with I being the identity matrix.
Traditionally, the first row and diagonal of NF are determined by actually constructing the flattened model and ascertaining the desired values from the flattened model by direct inversion of (I−F). Hence, if |M|=a and |S|=b, then |F|≈a+b. Due to the often-complex nature of the first moment matrices, the complexity of obtaining NF using traditional approaches is approximately O((a+b)3) while the space required to store the results is O((a+b)2). In view of this complexity, there exists a need in the art for a more efficient approach to calculating the first row and diagonal elements of NF.